package com.ztom.daily.n2022.m3;

/**
 * 蜡烛之间的盘子
 * <p>
 * https://leetcode-cn.com/problems/plates-between-candles/
 *
 * @author ZhangTao
 */
public class Day08PlatesBetweenCandles {

    public int[] platesBetweenCandles(String s, int[][] queries) {
        if (s == null || s.length() == 0 || queries == null || queries.length == 0) {
            return null;
        }

        int n = s.length();
        // 前缀和, 记录范围内有多少个 *
        int[] preSum = new int[n];
        // 记录 i 位置左侧最近的 |
        int[] left = new int[n];
        // 记录 i 位置右侧最近的 |
        int[] right = new int[n];

        for (int i = 0, j = n - 1, l = -1, r = -1, sum = 0;
             i < n;
             i++, j--) {
            if (s.charAt(i) == '*') {
                sum++;
            }
            preSum[i] = sum;

            if (s.charAt(i) == '|') {
                l = i;
            }
            left[i] = l;

            if (s.charAt(j) == '|') {
                r = j;
            }
            right[j] = r;
        }

        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int[] query = queries[i];
            // **|****|* [1,8]
            // 左边看右侧最近的 |
            int l = right[query[0]];
            // 右侧看左侧最近的 |
            int r = left[query[1]];
            // 必须两侧都有 |
            res[i] = l == - 1 || r == -1 || l >= r ? 0 : preSum[r] - preSum[l];
        }

        return res;
    }
}
